﻿#define _CRT_SECURE_NO_WARNINGS 1

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

// 你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储一位数字。
// 请你将两个数相加，并以相同形式返回一个表示和的链表
// 思路:将每个节点的值相加，因为是逆序，头结点就是低位的数字，相加之后，我们头插即可
// 注意最后需要判断进位carry是否为0，不为0需要进行头插
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = nullptr, * tail = nullptr;
        int carry = 0;
        while (l1 || l2)
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int sum = n1 + n2 + carry;
            if (head == nullptr)
            {
                head = tail = new ListNode(sum % 10);
            }
            else
            {
                tail->next = new ListNode(sum % 10);
                tail = tail->next;
            }
            carry = sum / 10;

            // 不为空就往后面走
            if (l1)
                l1 = l1->next;
            if (l2)
                l2 = l2->next;
        }

        if (carry > 0)
            tail->next = new ListNode(carry);

        return head;

    }
};

// 给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

//返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

// 思路: 将单词存在一个map中，此时已经按照字符的顺序排好了，这时只需要按照次数进行排序即可，
// 但是之前的相对顺序不能够改变，如果我们使用sort函数，因为sort函数是不稳定的，需要我们直接控制排序的逻辑
// 我们也可以使用稳定的排序stable_sort函数，但是由于两个函数中，pair有自己的比较规则，所以我们需要写一个仿函数
// 来控制我们比较的规则
// stable_sort函数的底层使用的归并排序

// 使用sort函数
class Solution {
public:
    struct Compare
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countmap;
        for (auto& word : words)
        {
            countmap[word]++;
        }

        vector<pair<string, int>> v;
        for (auto& kv : countmap)
        {
            v.push_back(make_pair(kv.first, kv.second));
        }

        sort(v.begin(), v.end(), Compare());
        vector<string> ret;
        for (size_t i = 0; i < k; ++i)
        {
            ret.push_back(v[i].first);
        }

        return ret;
    }
};

// 使用stable_sort函数
class Solution {
public:
    struct Compare
    {
        bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2)
        {
            return kv1.second > kv2.second;
        }
    };
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countmap;
        for (auto& word : words)
        {
            countmap[word]++;
        }

        vector<pair<string, int>> v;
        for (auto& kv : countmap)
        {
            v.push_back(make_pair(kv.first, kv.second));
        }

        stable_sort(v.begin(), v.end(), Compare());
        vector<string> ret;
        for (size_t i = 0; i < k; ++i)
        {
            ret.push_back(v[i].first);
        }

        return ret;
    }
};
int main()
{

    return 0;
}